package dichotomy;

public class BSAwesome {

    /**
     * 在无序数组 arr 中，相邻两个数字一定不相等，求数组arr中的局部最小值
     * 
     * @param arr
     * @return
     */
    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;// no exist!
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] > arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int L = 1;
        int R = arr.length - 2;
        int mid = 0;
        while (L < R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] > arr[mid - 1]) {
                R = mid - 1;
            } else if (arr[mid] < arr[mid + 1]) {
                L = mid + 1;
            } else {
                return mid;
            }
        }
        return mid;
    }

    public static void main(String[] args) {
        int[] a = { 11, 2, 1, 4, 2, 4, 5, 1, 6 };
        System.out.println(getLessIndex(a));
    }
}
